
/* License Notice:
**
** This program is free software: you can redistribute it and/or modify
**    it under the terms of the GNU General Public License as published by
**    the Free Software Foundation, either version 3 of the License, or
**    (at your option) any later version.
** This program is distributed in the hope that it will be useful,
**   but WITHOUT ANY WARRANTY; without even the implied warranty of
**   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
**   GNU General Public License for more details.
** You should have received a copy of the GNU General Public License
**   along with this program. If not, see <https://www.gnu.org/licenses/>.
*/

/**
 * @file linked_list_simple.hpp
 * @author TooOld2Rock'nRoll
 * @date dec/2004
 * @version 3.4.0
 *
 * @attention "make CFLAGS:=-DUNIT_TESTING" to run unit testing on the library.
 *
 * @see Cormen, Thomas H. (...) - Introduction to Algorithms (2ºed)
 * @see Deitel, H. M. (...) - How to Program C++ (3ªed)
 * @see https://cpputest.github.io/manual.html
 *
 * @todo maybe add a sort function!
 *
 * @brief Header file for the <i>Simple</i> version Linked List data structure.
 */
#ifndef LLIST_S_HPP
#define LLIST_S_HPP

/*---- Includes ----*/
#include <stdexcept>
#include <fmt/core.h>

#ifdef UNIT_TESTING
#include <CppUTest/CommandLineTestRunner.h>
#include <CppUTest/MemoryLeakDetectorNewMacros.h>
#endif

/*---- Defines ----*/


/*---- Enumerations ----*/


/*---- Typedefs ----*/


/*---- Class Declaration ----*/
/**
 * @brief Fast Linked List data structure.
 * @see https://en.wikipedia.org/wiki/Linked_list
 *
 * A linked list is a dynamic collection of (usually) unordered nodes that are accessed sequentially from head to tail.<br>
 *
 * This algorithm is simples in the sense that it covers the most basic requirements to be considered a functional linked
 *   list and it is <b>not</b> thread safe (traversing the list in parallel would break the reading head logic).<br>
 * This algorithm is also fast by only saving references to user data removing a good overhead of consistency checks,
 *   but this is not safe and difficult to debug in case of errors. Consider using the Safe version if such safeguards
 *   are necessary in your project.<br>
 *
 * The insert() function adds a new node to the list at different position references.<br>
 * The remove() function takes out a list's node at different position references.<br>
 * The next() function moves the read head forward.<br>
 * The other functions are just helpers that make some jobs easier.<br>
 * A report will be printed on destruct if LLSI_ENABLE_BENCHMARK flag is active.<br>
 *
 * Example:
 * <code>
 *   int *x = nullptr, *buff = nullptr;
 *   LinkedList_Si<int> TheList;
 *
 *   x = new int (10);
 *   TheList.insert (x);
 *
 *   x = new int (20);
 *   TheList.insert (x);
 *
 *   TheList.reset (); //read head points to first package
 *   TheList.next (); //read head points to second package
 *   buff = TheList.remove (); //remove second package (the one under the read head)
 *   //buff == 10
 *   delete (buff);
 *
 *   //10 remains and will be dealt with in the destructor.
 *
 *   //a report may be printed
 * </code>
 *
 *  -Statistics:<br>
 *      Linked List Statistics Report:<br>
 *      Total Used Time: 12.9610s
 *          Insert<br>
 *            -was called 50000 times.<br>
 *            -total used time: 0.009000s<br>
 *            -Average Delay: 0.000180ms<br>
 *          Remove<br>
 *            -was called 50000 times.<br>
 *            -total used time: 0.010000s<br>
 *            -Average Delay: 0.000200ms<br>
 *          Search<br>
 *            -was called 50000 times.<br>
 *            -total used time: 12.942000s<br>
 *            -Average Delay: 0.258840ms<br>
 *     -Machine Specs:<br>
 *        Intel Core i7-7700HQ CPU @ 2.80GHz<br>
 *        16Gb RAM<br>
 *
 * @tparam T - data type to be stored in the list.
 */
template <typename T>
class LinkedList_Si
{
    public:
        /**
         * @brief Optional user callback to compare list packages with search data.
         *
         * A barebones search callback would look like this:
         * <code>
         *  bool myPackageSearchCB (T *node_package, const T *key)
         *  { return (*pkgKey == *key); }
         * </code>
         *
         * And it would be used like this:
         * <code> thePackage = myList->search (&key2find, (LinkedList_Si::SearchNodeCallback)myPackageSearchCB); </code>
         *
         * @param node_package - the node package to compare.
         * @param user_data - pointer to what ever the user needs to find the correct node.
         *
         * @return Callback must return <b>true</b> to stop search when package is found or <b>false</b> to continue.
         */
        typedef bool (*SearchNodeCallback) (T &node_package, const void *user_data);


    private:
        //the node structure that builds the linked list
        struct node_s
        {
            T *tp_package = nullptr; //user data
            LinkedList_Si::node_s *p_next = nullptr; //pointer to next node or null if last one
        };//end node

        std::size_t _size = 0;//the number of nodes in the list

        LinkedList_Si::node_s *p_head = nullptr; //first node of the list or null if empty

        LinkedList_Si::node_s *p_readhead = nullptr; //current node being read
        LinkedList_Si::node_s *p_aux_node = nullptr; //keeps track of previous node, required for remove!


    protected:


    public:
        /** @brief Start a new List. */
        // LinkedList_Si () {  }
        ~LinkedList_Si ();

        void insert (T *package);
        T * reset ();
        T * remove ();
        T * read () const;
        T * next ();
        T * swap (T *new_package);

        T * search (const T &key);
        T * search (const void *data, LinkedList_Si::SearchNodeCallback search_cb);
        void clean (bool del_packages);

        /** @brief Returns <b>true</b> if list is empty, <b>false</b> otherwise. */
        bool empty () const { return (this->_size == 0); }
        /** @brief Returns the number of nodes stored in the list. */
        std::size_t size () const { return this->_size; }
};//END LinkedList_Si


//it is truly a monstrosity to implement an entire library in a header file!
//but using templates "requires" it....
/*---- Methods Definition ----*/
/**
 * @brief Delete all nodes and free all data in the List.
 *
 * @warning If the list is not empty, all the stored user packages will be freed to avoid memory leaks!
 */
template <typename T>
LinkedList_Si<T>::~LinkedList_Si ()
{
    this->clean (true);
}//End Destructor


/**
 * @brief Push a new package to the head of the List.
 *
 * @warning The data on the new package will <b>NOT</b> be copied, only the reference saved!
 *
 * @param package - data pointer to be saved.
 *
 * @throws std::invalid_argument - if the new package is null (it makes no sense!).
 */
template <typename T>
void LinkedList_Si<T>::insert (T *package)
{
    //New node to put in this
    LinkedList_Si::node_s *new_node = nullptr;

    //check parameters
    if (!package)
        throw std::invalid_argument (fmt::format ("{0}:{1} - new package is NULL!", __LINE__, __FILE__));

    //Save information passed to function
    new_node = new LinkedList_Si::node_s ();
    new_node->tp_package = package;

    new_node->p_next = this->p_head; //move list head
    this->p_head = new_node; //new list head

    ++this->_size; //Increase list Size;
}//End insert ()


/**
 * @brief Resets the reading head to the first node.
 *
 * @return Pointer to the package at the list head or null if empty.
 */
template <typename T>
T * LinkedList_Si<T>::reset ()
{
    this->p_readhead = this->p_head;
    this->p_aux_node = nullptr;

    return (this->p_readhead ? this->p_readhead->tp_package : nullptr);
}//End reset ()


/**
 * @brief Removes the package under the read head from the list and increment the reading head's position.
 * @remark Client is responsible for freeing the returned pointer, we're only storing it!
 *
 * @return Pointer to the package under read head, null if at the end of the list or if list is empty.
 */
template <typename T>
T * LinkedList_Si<T>::remove ()
{
    T *save = nullptr;

    //check parameters
    if (!this->p_head)
        return nullptr;
    else if (!this->p_readhead)
    {
        // _debug ("WARNING, read head pointing to end of the list, nothing to remove!");
        return nullptr;
    }//end else if (!this->_readhead)

    //save node package and free node
    save = this->p_readhead->tp_package;
    if (this->p_aux_node)
        this->p_aux_node->p_next = this->p_readhead->p_next;
    else //read head under first node!
        this->p_head = this->p_readhead->p_next;

    delete (this->p_readhead);
    --this->_size;

    //reposition readhead
    this->p_readhead = (this->p_aux_node ? this->p_aux_node->p_next : this->p_head);

    return save;
}//End remove ()


/**
 * @brief Reads the package under the read head.
 *
 * @return Pointer to the package under the read head, null if at the end of the list or if list is empty.
 */
template <typename T>
T * LinkedList_Si<T>::read () const
{
    //check parameters
    if (!this->p_head)
    {
        // _debug ("INFO: list is empty, nothing to read.");
        return nullptr;
    }//end if (!this->_head)
    else if (!this->p_readhead)
    {
        // _debug ("WARNING: end of list reached, reset to start over.");
        return nullptr;
    }//end if (!this->_readhead)

    return this->p_readhead->tp_package;
}//End read ()


/**
 * @brief Increments the read head position to the next node.
 * @remarks null will be returned <i>once</i> to mark the end of the list, the next call will reset to the first node.
 *
 * @return Pointer to the next package on the list, null if at the end of the list or if list is empty.
 */
template <typename T>
T * LinkedList_Si<T>::next ()
{
    //check parameters
    if (!this->p_head)
    {
        // _debug ("INFO: list is empty, nothing to read.");
        return nullptr;
    }//end if (!this->_head)

    this->p_aux_node = this->p_readhead;
    //if end of list reached on previous call, redirect head to first
    this->p_readhead = (this->p_readhead ? this->p_readhead->p_next : this->p_head);

    return (this->p_readhead ? this->p_readhead->tp_package : nullptr);
}//End next ()


/**
 * @brief Swaps the package under the read head for a new one.
 * @remarks Client is responsible for freeing the returned package pointer as they created it!
 *
 * @param new_package - data pointer to be saved in the list in place of the current one.
 *
 * @return Pointer to the old package under read head, null if at the end of the list or if list is empty.
 *
 * @throws std::invalid_argument - if the new package is null (it makes no sense!).
 */
template <typename T>
T * LinkedList_Si<T>::swap (T *new_package)
{
    T *old_package = nullptr;

    //check parameters
    if (!new_package)
        throw std::invalid_argument (fmt::format ("{0}:{1} - new package is null!", __LINE__, __FILE__));
    else if (!this->p_head)
    {
        // _debug ("WARNING, List is empty, nothing to be done.");
        return nullptr;
    }//end else if (!this->_head)
    else if (!this->p_readhead)
    {
        // _debug ("WARNING, read head pointing to end of the list, nothing to swap with!");
        return nullptr;
    }//end else if (!this->_readhead)

    old_package = this->p_readhead->tp_package;
    this->p_readhead->tp_package = new_package;

    return old_package;
}//End swap ()


/**
 * @brief Search for a package in the list.
 *
 * The search will begging from the read head current position till the end of the list (remember to call reset before
 *   starting the search).<br>
 * The read head will stay at the position it stopped when the method returns, so you may repeat the search from that
 *   point, maybe to find more nodes with the same pattern (just remember to increment the reading head position or
 *   search will be stuck at the same node).
 *
 * @param key - key to search the list packages to (compare operator will be used).
 *
 * @return Pointer to the matched package or null if no match is found.
 */
template <typename T>
T * LinkedList_Si<T>::search (const T &key)
{
    //check parameters
    if (!this->p_head)
    {
        // _debug ("INFO, List is empty, nothing to be done.");
        return nullptr;
    }//end else if (!this->_head)

    do {
        if (*this->p_readhead->tp_package == key)
            break; //found the node
    } while (this->next ());

    return (this->p_readhead ? this->p_readhead->tp_package : nullptr);
}//End search ()


/**
 * @brief Search for a package in the list using a custom callback.
 *
 * The search will begging from the read head current position till the end of the list (remember to call reset before
 *   starting the search).<br>
 * The read head will stay at the position it stopped when the method returns, so you may repeat the search from that
 *   point, maybe to find more nodes with the same pattern (just remember to increment the reading head position or
 *   search will be stuck at the same node).
 *
 * @param data - client data to be passed to search the callback.
 * @param search_cb - the client search callback to compare the searched data with the packages.
 *
 * @return Pointer to the matched package or null if no match is found.
 *
 * @throws std::invalid_argument - if the new search callback is null (it makes no sense!).
 */
template <typename T>
T * LinkedList_Si<T>::search (const void *data, LinkedList_Si::SearchNodeCallback search_cb)
{
    //check parameters
    if (!search_cb)
        throw std::invalid_argument (fmt::format ("{0}:{1} - search callback is null!", __LINE__, __FILE__));
    else if (!this->p_head)
    {
        // _debug ("INFO, List is empty, nothing to be done.");
        return nullptr;
    }//end else if (!this->_head)

    do {
        if (search_cb (*this->p_readhead->tp_package, data))
            break; //found the node
    } while (this->next ());

    return (this->p_readhead ? this->p_readhead->tp_package : nullptr);
}//End search ()


/**
 * @brief Remove all nodes from the list.
 *
 * @param del_packages - if the method should deallocate the package pointers for the user or not.
 */
template <typename T>
void LinkedList_Si<T>::clean (bool del_packages)
{
    //check parameters
    if (!this->p_head)
    {
        // _debug ("INFO, List is empty, nothing to clean.");
        return;
    }//end else if (!this->_head)

    do {
        //remove the first node from the list
        this->p_readhead = this->p_head;
        this->p_head = this->p_head->p_next;

        //free the resources
        if (del_packages)
            delete (this->p_readhead->tp_package);
        delete (this->p_readhead);

        --this->_size;
    } while (this->p_head);

    this->p_readhead = nullptr;
}//End clean ()

#endif //LLIST_S_HPP

